package com.hackerrank.challenges.alienlanguages;

import java.util.Scanner;

public class Solution {
	private static final int MAX = 100000007;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		for(int i = 0; i < t; i++) {
			int n = in.nextInt(), m = in.nextInt(), fp[] = new int[n];
			for(int k = n - 1; k >= n / 2; k--)
				fp[k] = n - k;
			for(int k = 0; k < n / 2; k++)
				fp[k] = (n + 1) / 2;
			for(int j = 1; j < m; j++) {
				int fc[] = new int[n], k = n - 1;
				fc[k] = fp[0];
				for(k--; k >= n / 2; k--)
					fc[k] = (fc[k + 1] + fp[0]) % MAX;
				for(k = n / 2 - 1; k >= 0; k--)
					fc[k] = (fc[k + 1] + fp[2 * k + 1]) % MAX;
				fp = fc;
			}
			System.out.println(fp[0]);
		}
	}
}
